from sys import stdin,argv
from random import randint

def testing(arr):
	"""Bad algorithm"""
	best = acc = arr[0]
	for x in arr[1:]:
		acc += x
		if acc>best:
			best = acc
		elif acc<0:
			acc = 0
	return best

def square(arr):
	"""Trivial naive implementation"""
	best = None
	for i in range(0, len(arr)):
		for j in range(i, len(arr)):
			s = 0
			for k in range(i, j+1):
				s += arr[k]
			if best==None or best<s:
				best = s
	return best

def linear(arr):
	"""Optimized implementation"""
	fsm = ssm = arr[0]
	for x in arr[1:]:
		fsm = max(x, fsm+x)
		if fsm>ssm: ssm = fsm
	return ssm

def gen(sz, lb, ub):
	"""Generates a list of sz int in [lb, ub]"""
	arr = []
	for i in range(sz+1):
		arr.append(randint(lb, ub))
	return arr


if len(argv)==2:
	if argv[1].isdigit():
		ct = int(argv[1])
		fails = 0
		for i in range(ct):
			arr = gen(20, -5, 10)
			a = testing(arr)
			b = linear(arr)
			if a != b:
				print arr
				fails += 1
		if fails==0:
			print "It looks like the tested algorithm works!"
		else:
			print "Failures:", fails, "/", ct, "tests"
	else:
		print "Please provide a number of tests or no parameter at all."
else:
	arr = map(lambda x: int(x), stdin.readlines())
	print "The linear algorithm says", linear(arr)
	print "The tested algorithm says", testing(arr)
